Fecho transitivo

Na matemática, o fecho transitivo de uma relação binária R sobre um conjunto X é a relação transitiva R⁺ sobre o conjunto X de maneira que R⁺ contém R e R⁺ é mínimo (Lidl and Pilz 1998:337). Se a própria relação binária é transitiva, então o fecho transitivo é a própria relação; senão, o fecho transitivo é uma outra relação. Por exemplo, se X é um conjunto de aeroportos e x R y significa "existe um voo direto do aeroporto x para o aeroporto y", então o fecho transitivo de R sobre X é a relação R⁺: "é possível voar a partir de x para y em um ou mais voos."

Relações transitivas e exemplos

Uma relação transitiva R sobre um conjunto X é transitiva se, para todo x,y,z em X, sempre que x R y e y R z então x R z. Exemplos de relações transitivas incluem a relação de igualdade em qualquer conjunto, a relação "menor ou igual que" em qualquer conjunto linearmente ordenado, e a relação "x nasceu antes de y" no conjunto de todas as pessoas. Simbolicamente, isso pode ser descrito como: se x < y ey < z, então x < z.

Um exemplo de uma relação intransitiva é "a cidade x é alcançável através de um voo direto a partir da cidade y" no conjunto de todas as cidades. Simplesmente por haver um voo direto de uma cidade para uma segunda, e também um voo direto dessa segunda cidade para uma terceira, não implica haver um voo direto da primeira cidade para a terceira. O fecho transitivo dessa relação é uma relação diferente, que é "existe uma sequência de voos diretos que começa na cidade x e termina na cidade y". Toda relação pode ser estendida de maneira semelhante para uma relação transitiva.

Existência e descrição

Para qualquer relação R, o fecho transitivo de R sempre existe. Para comprovar isso, note que a interseção de qualquer família de relações transitivas é novamente transitiva. Além disso, existe ao menos uma relação transitiva contendo R,

Para conjunto finitos, podemos construir o fecho transitivo passo a passo, começando por R e adicionando arestas transitivas. Isso nos dá a ideia para a construção geral. Para qualquer conjunto X, podemos provar que o fecho transitivo é dado pela seguinte expressão

$R^{+}=\bigcup _{i\in \{1,2,3,\ldots \}}R^{i}.$

onde $R^{i}$ é a i-ésima potência de R, definida através de indução por

$R^{1}=R\,\!$

e, para $i>0$,

$R^{i+1}=R\circ R^{i}$

onde $\circ$ representa a composição de relações.

Para mostrar que a definição de R⁺ mostrada acima é a menor relação transitiva contendo R, mostramos que ela contém R, que é transitiva, e que é o menor conjunto com ambas as características.

• $R\subseteq R^{+}$: $\displaystyle R^{+}$ contém contém todas $\displaystyle R^{i}$, particularmente $\displaystyle R^{+}$ contém $\displaystyle R$.
• $\displaystyle R^{+}$ é transitiva: todo elemento de $\displaystyle R^{+}$ está em um dos $\displaystyle R^{i}$, então $\displaystyle R^{+}$ deve ser transitivo pela seguinte razão: se $(s_{1},s_{2})\in R^{j}$ e $(s_{2},s_{3})\in R^{k}$, então pela composição associativa, $(s_{1},s_{3})\in R^{j+k}$ (logo, em $\displaystyle R^{+}$) por conta da definição de $\displaystyle R^{i}$.
• $\displaystyle R^{+}$ é mínima: Seja $\displaystyle G$ qualquer relação transitiva contendo $\displaystyle R$, queremos mostrar que $R^{+}\subseteq G$. Isso é suficiente para mostrar que $i>0$, $R^{i}\subseteq G$. Bem, já que $\displaystyle G$ contém $\displaystyle R$, $R^{1}\subseteq G$. E como $\displaystyle G$ é transitiva, para qualquer $R^{i}\subseteq G$, $R^{i+1}\subseteq G$ de acordo com a construção de $R^{i}\,\!$ e que é transitivo. Logo, por indução, $\displaystyle G$ contém todo $R^{i}\,\!$, e também contém $\displaystyle R^{+}$.

Propriedades

A interseção de duas relações transitivas é transitiva.

A união de duas relações transitivas não pode ser transitiva. Para preservar a transitividade, uma delas precisa manter o fecho transitivo. Isso ocorre, por exemplo, quando geramos a união de duas relações de equivalência ou duas relações de pré-ordem. Para obter uma nova relação de equivalência ou pré-ordem uma precisa manter o fecho transitivo (reflexividade e simetria—no caso de relações de equivalência—são automáticas).

Na teoria dos grafos

O fecho transitivo construindo o grafo de retorno a partir do grafo de entrada.

Na ciência da computação, o conceito de fecho transitivo pode ser pensado como a construção de uma estrutura de dados que possibilita responder problemas de atingibilidade. Isso é, será possível chegar à um nó b, partindo de um nó a em um ou mais saltos? Uma relação binária apenas informa que esse nó a está conectado ao nó b, e que o nó b está conectado ao nó c, etc. Após o fecho transitivo ser construído, como mostrado na figura abaixo, em uma operação O(1) pode se determinar que o nó d é atingível a partir do nó a. A estrutura de dados é geralmente armazenada como uma matriz, então se matriz[1][4] = 1, significa que o nó 4 é atingível a partir do nó 1 e um ou mais saltos.

O fecho transitivo de um grafo acíclico direcionado (GAD) é a relação de atingibilidade do GAD e uma ordem parcial estrita.

Na lógica e na complexidade computacional

O fecho transitivo de uma relação binária não pode, geralmente, ser expresso em lógica de primeira ordem (LPO). Isso significa que não é possível escrever uma fórmula usando predicados R e T que serão satisfatíveis em qualquer modelo se e somente se T é o fecho transitivo de R.

Na teoria dos modelos finitos, lógica de primeira ordem (LPO) estendida com um operador de fecho transitivo é normalmente chamada lógica de fecho transitivo, e abreviada LPO(FT) ou apenas FT.

Na teoria da complexidade computacional, a classe NL corresponde precisamente ao conjunto de sentenças lógicas que podem ser expressas em FT. Isso acontece porque a propriedade do fecho transitivo tem uma relação próxima com o problema NL-Completo da conectividade st, para achar caminhos direcionados em um grafo. Similarmente, a classe L é de lógica de primeira ordem com fecho transitivo e comutativo. Quando o fecho transitivo é adicionado à lógica de segunda ordem, obtemos PSPACE.

Em linguagens de consulta à banco de dados

Desde os anos 1980 o Oracle database implementa uma extensão SQL prioritária CONNECT BY... START WITH que permite a computação de um fecho transitivo como parte de uma consulta. O padrão SQL 3 (1999) um um construtor mais generalizado WITH RECURSIVE permitindo fechos transitivos serem computados dentro do processador de consultas; em 2011 esse último foi implementado por IBM DB2, Microsoft SQL Server, e PostgreSQL, entretanto não pelo MySQL (Benedikt and Senellart 2011:189).

Datalog também implementa computações transitivamente fechadas. (Silberschatz et al. 2010:C.3.6).

Algoritmos

Algoritmos eficientes para computar o fecho transitivo de um grafo podem ser encontrados em Nuutila (1995). A técnica mais simples é provavelmente o Algoritmo de Floyd-Warshall. O métodos de pior caso mais rápidos, que não são praticamente viáveis, reduzem o problema à uma multiplicação de matrizes.

Bibliografia

• Lidl, R. and Pilz, G., 1998, Applied abstract algebra, 2nd edition, Undergraduate Texts in Mathematics, Springer, ISBN 0-387-98290-6
• Keller, U., 2004, Some Remarks on the Definability of Transitive Closure in First-order Logic and Datalog (unpublished manuscript)
• Erich Grädel; Phokion G. Kolaitis; Leonid Libkin; Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema, Scott Weinstein (2007). Finite Model Theory and Its Applications. [S.l.]: Springer. pp. 151–152. ISBN 978-3-540-68804-4 
• Libkin, Leonid (2004), Elements of Finite Model Theory, ISBN 978-3-540-21202-7, Springer 
• Heinz-Dieter Ebbinghaus; Jörg Flum (1999). Finite Model Theory 2nd ed. [S.l.]: Springer. pp. 123–124, 151–161, 220–235. ISBN 978-3-540-28787-2 
• Aho, Alfred V.; Jeffrey D. (1 de janeiro de 1979). «Universality of Data Retrieval Languages». New York, NY, USA: ACM. Proceedings of the 6th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages: 110–119. doi:10.1145/567752.567763 
• Benedikt, Michael; Senellart, Pierre (1 de janeiro de 2011). Edward K., ed. Databases. [S.l.]: Springer New York. p. 169-229. ISBN 978-1-4614-1167-3. doi:10.1007/978-1-4614-1168-0_10 
• Nuutila, E., Efficient Transitive Closure Computation in Large Digraphs. Acta Polytechnica Scandinavica, Mathematics and Computing in Engineering Series No. 74, Helsinki 1995, 124 pages. Published by the Finnish Academy of Technology. ISBN 951-666-451-2, ISSN 1237-2404, UDC 681.3.
• Abraham Silberschatz; Henry Korth; S. Sudarshan (2010). Database System Concepts 6th ed. [S.l.]: McGraw-Hill. ISBN 978-0-07-352332-3  Appendix C (online only)
• Foto N. Afrati, Vinayak Borkar, Michael Carey, Neoklis Polyzotis, Jeffrey D. Ullman, Map-Reduce Extensions and Recursive Queries, EDBT 2011, March 22–24, 2011, Uppsala, Sweden, ISBN 978-1-4503-0528-0

Ligações externas

• "Transitive closure and reduction", The Stony Brook Algorithm Repository, Steven Skiena.